﻿using AlgLrnLib.Sorting;

namespace AlgLrnLib.Searching
{
    public class BinarySearch : BaseSearch
    {
        public override int FindIndex(int[] numbers, int number, DebugTraceDelegate DEBUG_TRACE)
        {
            MergeSort sort = new MergeSort();
            numbers = sort.SortAsc(numbers, DEBUG_TRACE);

            return SplitAndSearch(numbers, number, 0, numbers.Length - 1, DEBUG_TRACE);
        }

        private int SplitAndSearch(int[] numbers, int number, int nStartIdx, int nEndIdx, DebugTraceDelegate DEBUG_TRACE)
        {
            if (nStartIdx == nEndIdx) // only one element
                return number == numbers[nStartIdx] ? nStartIdx : -1;

            int nMiddleIdx = (nStartIdx + nEndIdx) / 2; // same as nStartIdx + (nEndIdx - nStartIdx) / 2;

            if (number == numbers[nMiddleIdx])
                return nMiddleIdx;

            if (number > numbers[nMiddleIdx])
                return SplitAndSearch(numbers, number, nMiddleIdx + 1, nEndIdx, DEBUG_TRACE);
            else if (number < numbers[nMiddleIdx])
                return SplitAndSearch(numbers, number, nStartIdx, nMiddleIdx, DEBUG_TRACE);

            return nMiddleIdx; // if numbers is not smaller or bigger than numbers[nMiddleIdx] then it is equal to numbers[nMiddleIdx]
        }
    }
}
